package com.ronz.binarytree;

import java.util.Arrays;

/**
 * @Description 堆排序
 * @Author Ronz
 * @Date 2021/1/19 16:28
 * @Version 1.0
 */
public class No4_HeapSort {

    public static void main(String[] args) {
        int arr[] = { 6, 5, 2, 7, 3, 9, 8 };

        heapSort(arr);

        System.out.println(Arrays.toString(arr));
    }


    /**
     * 堆排序
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr){
        for (int i=arr.length; i>1; i--){   // 循环执行，直到只剩下一个元素
            buildHeap(arr, i);  // 构建（或调整）堆
            swap(arr, 0, i-1);    // 交换堆顶和最后一个元素
        }
    }

    /**
     * 创建最大堆
     * @param arr 待排序数组
     * @param length 待排序数组元素长度
     */
    public static void buildHeap(int[] arr, int length){

        for (int i=length/2-1; i>=0; i--){  // 对所有的非叶子节点都来一遍，首先从最后一个开始
            int k = i*2+1;  // 非叶子节点的左子节点
            if (k+1 < length && arr[k] <= arr[k+1]){ // 找出左、右子节点中最大的节点的索引
                k++;
            }
            if (arr[i] < arr[k]){   // 如果父节点小于子节点
                swap(arr, i, k);    // 交换元素
            }
        }


    }

    /**
     * 交换数组中的两个元素
     * @param arr 待交换元素的数组
     * @param i 待交换元素的索引
     * @param j 待交换元素的索引
     */
    public static void swap(int[] arr, int i, int j){
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
